1. Field of the Invention
This invention relates to a method for making safe an electronic assembly involving a cryptographic algorithm using a secret key. More precisely, the method aims at achieving a version of the algorithm that is not damageable by some types of physical attacks—called High-Order Differential Power Analysis—trying to obtain information on the secret key after studying the electric consumption of the electronic assembly during the running of computation.
2. Description of the Related Art
The cryptographic algorithms considered here use a secret key to calculate an output information according to an input information; this may be a coding, decoding, signature, check of the signature, authentification or non-repudiation operation. They are made so that an aggressor, knowing the inputs and outputs, may not practically deduct any information concerning the secret key itself.
Thus it is a question of a larger category than the one classically designated by the expression algorithms with a secret key or symmetrical algorithms. In particular, anything described in this patent application also applies to algorithms said to be with a public key or unsymmetrical algorithms, which actually have two keys: one is public, the other private, not disclosed, the last one being that aimed at by the aggressions described hereunder.
The aggressions of the type Power Analysis start from the fact that really the aggressor may acquire information other than the simple release of inputs and outputs, when calculation is carried out, as for instance the electrical consumption of the micro controller or the electromagnetic radiation produced by the circuit.
The differential electrical consumption analysis is the principle of a category of attacks called Differential Power Analysis, DPA in short, enabling to obtain information on the secret key contained in the electronic assembly, by making a statistical analysis of electrical consumption recordings made over many calculations with the same key.
In the simplest attack, called “DPA of the first order” or simply “DPA” when there is no confusion possible, the attacker records current consumption signals and calculates the individual statistical properties for the signal at each moment. Here we consider the attacks called High-Order Differential Power Analysis, HO-DPA in short, generalising the “DPA of the first order” attack: the aggressor now calculates the joint statistical properties of the electrical consumption taken at several different times. More precisely, a n-order DPA attack take into account n values of the consumption signal, corresponding to n different intermediate values, that appear during the calculation of the cryptographic algorithm. The intermediate values detected by attacks will be named in the following text, critical information.
Is considered, as a non-limiting example, the case of the DES algorithm (Data Encryption Standard), which is described in FIPS PUB 46-2, Data Encryption Standard, 1994, a document mentioned as a reference.
The DES algorithm runs in 16 steps called rounds (see FIG. 2). In each of the 16 rounds, a conversion f is made with 32 bits. This conversion f uses eight non linear conversions of 6 bits over 4 bits, coded each in a table called S-box (S on FIG. 2)
A DPA attack of the second order on the DES may be executed as follows:
In a first step, consumption measurements are made over the first round, for 1000 DES calculations. E[1], . . . , E[1000] should be noted as input values for these 1000 calculations. C[1], . . . , C[1000] should be noted as the 1000 corresponding curves of electrical consumption measured when making these calculations.
In a second step, let us suppose that two bits (being critical information), with a respective value b1 and b2, appear during the calculations and are such that b1 ⊕ b2 equal the value b of the first output bit from the first S-box over the first round. Here, ⊕ designates the function “OR-exclusive” bit by bit. An assumption is made on the δ time interval between the time where there is the consumption curve point corresponding to b1 and that corresponding to b2. Then is associated with each curve C[i] where i is an integer successively equal to 1, 2, . . . , 1000, an other curve Cδ[i] equal to the difference between C[i] and the curve obtained from C[i] by translation of a δ value along the X-axis. The average CM curve of the 1000 Cδ[i] curves is also calculated.
In a third step, it is easy to see that b only depends on 6 bits of the secret key. The aggressor makes a supposition concerning the 6 bits. He calculates—from those 6 bits and the E[i]—the theoretical values expected for b. This allows a separation of the 1000 inputs E[1], . . . , E[1000] into two classes: those leading to b=O and those leading to b=1.
In a fourth step, a calculation is then made of the CM′ average (respectively CM″) of the Cδ [i] curves relating to inputs of the first class (respectively the second class), i.e. for which b=0 (respectively b=1). If CM′ and CM″ show a large difference, it is considered that the values taken for the 6 bits in the key, as well as the choice of the δ value were the correct ones. If CM′ and CM″ show no great difference, in the statistical meaning, i.e. no difference clearly higher than the typical offset for the measured noise, the second step is restarted with another choice for the 6 bits. If no choice for the key 6 bits is valid, steps 3 and 4 are restarted with another choice for δ.
In a fifth step, the steps 2, 3 and 4 are repeated with two bits from where the “or-exclusive” is out of the second S-box, then the third S-box, . . . , up to the eighth S-box. Finally 48 bits of the secret key are thus obtained.
In a sixth step, the 8 remaining bits may be found using a thorough search.
Theoretically, the DPA of the n order does not require any knowledge of the individual electrical consumption for each instruction, nor of the position in time for each instruction. It similarly applies when it is estimated that the attacker knows some algorithm outputs and the corresponding consumption curves. It is only based on the basic supposition that:
There is a set of n intermediate variables, that appears during the algorithm calculation, such as the knowledge of a few key bits, practically less than 32 bits, allowing to decide if two inputs, and respectively two outputs, lead or not to the same value for a known function of these n variables.
All the algorithms using S-boxes, such as the DES, are potentially vulnerable by the “High Order DPA”, as the usual embodiment modes, including those designed to resist “DPA of the first order” attacks, remain generally under the above mentioned hypothesis.
Practically, the installation requires also finding (through a thorough search or the knowledge of other information, for instance the detail of the cryptographic algorithm implementation) the time intervals between the consumption curve points which correspond to the n variables considered.
An aim of this invention is to eliminate any risk of “DPA of the n order” attacks, for all values of n, of sets or cryptography electronic systems with a secret or private key.
Another aim of this invention is to give protection for the cryptography electronic systems such as the basic hypothesis above mentioned is not verified anymore, i.e. no known function of a set of n intermediate variables depends on the knowledge of an easily accessible subset of the secret or private key, with the “High Order DPA” attacks being thus inoperative.